package com.ilia.rubik;

import java.util.*;

public class Cube {

  public static String nr = "\n";


  public final static int F1 = 0;
  public final static int F2 = 1;
  public final static int F3 = 2;
  public final static int F4 = 3;
  public final static int F5 = 4;
  public final static int F6 = 5;
  public final static int F7 = 6;
  public final static int F8 = 7;
  public final static int F9 = 8;

  public final static int U1 = 9;
  public final static int U2 = 10;
  public final static int U3 = 11;
  public final static int U4 = 12;
  public final static int U5 = 13;
  public final static int U6 = 14;
  public final static int U7 = 15;
  public final static int U8 = 16;
  public final static int U9 = 17;

  public final static int R1 = 18;
  public final static int R2 = 19;
  public final static int R3 = 20;
  public final static int R4 = 21;
  public final static int R5 = 22;
  public final static int R6 = 23;
  public final static int R7 = 24;
  public final static int R8 = 25;
  public final static int R9 = 26;

  public final static int D1 = 27;
  public final static int D2 = 28;
  public final static int D3 = 29;
  public final static int D4 = 30;
  public final static int D5 = 31;
  public final static int D6 = 32;
  public final static int D7 = 33;
  public final static int D8 = 34;
  public final static int D9 = 35;

  public final static int L1 = 36;
  public final static int L2 = 37;
  public final static int L3 = 38;
  public final static int L4 = 39;
  public final static int L5 = 40;
  public final static int L6 = 41;
  public final static int L7 = 42;
  public final static int L8 = 43;
  public final static int L9 = 44;

  public final static int B1 = 45;
  public final static int B2 = 46;
  public final static int B3 = 47;
  public final static int B4 = 48;
  public final static int B5 = 49;
  public final static int B6 = 50;
  public final static int B7 = 51;
  public final static int B8 = 52;
  public final static int B9 = 53;

  public final static int CUBE_CELLS = 54;

  public static int[] copy(int[] source) {
    int[] res = new int[source.length];
    for (int i = 0; i < res.length; i++) {
      res[i] = source[i];
    }
    return res;
  }
  
  public static void copy(int[] source, int[] target) {
	    for (int i = 0; i < target.length; i++) {
	    	target[i] = source[i];
	    }
	  }


  /*
  public int[][] F_pattern = {
    { F1, F},
    { F2, F},
    { F3, F},
    { F4, F},
    { F5, F},
    { F6, F},
    { F7, F},
    { F8, F},
    { F9, F},

    { U1, },
    { U2, },
    { U3, },
    { U4, },
    { U5, },
    { U6, },
    { U7, },
    { U8, },
    { U9, },

    { R1, },
    { R2, },
    { R3, },
    { R4, },
    { R5, },
    { R6, },
    { R7, },
    { R8, },
    { R9, },

    { L1, },
    { L2, },
    { L3, },
    { L4, },
    { L5, },
    { L6, },
    { L7, },
    { L8, },
    { L9, },

    { D1, },
    { D2, },
    { D3, },
    { D4, },
    { D5, },
    { D6, },
    { D7, },
    { D8, },
    { D9, },

    { B1, },
    { B2, },
    { B3, },
    { B4, },
    { B5, },
    { B6, },
    { B7, },
    { B8, },
    { B9, },

  };

  */
  public static int[][] F_pattern = {
    { F1, F7},
    { F2, F4},
    { F3, F1},
    { F4, F8},
    { F6, F2},
    { F7, F9},
    { F8, F6},
    { F9, F3},

    { U7, L9},
    { U8, L6},
    { U9, L3},

    { R1, U7},
    { R4, U8},
    { R7, U9},

    { L3, D1},
    { L6, D2},
    { L9, D3},

    { D1, R7},
    { D2, R4},
    { D3, R1},
  };

  public static int[][] Fm_pattern = reverse_pattern(F_pattern);

  public static int[][] R_pattern = {
    { R1, R7},
    { R2, R4},
    { R3, R1},
    { R4, R8},
    { R6, R2},
    { R7, R9},
    { R8, R6},
    { R9, R3},

    { U3, F3},
    { U6, F6},
    { U9, F9},

    { F3, D3},
    { F6, D6},
    { F9, D9},

    { D3, B3},
    { D6, B6},
    { D9, B9},

    { B9, U9},
    { B6, U6},
    { B3, U3},
  };
  public static int[][] Rm_pattern = reverse_pattern(R_pattern);

  public static int[][] B_pattern = {
    { B1, B7},
    { B2, B4},
    { B3, B1},
    { B4, B8},
    { B6, B2},
    { B7, B9},
    { B8, B6},
    { B9, B3},

    { R3, D9},
    { R6, D8},
    { R9, D7},

    { U3, R9},
    { U2, R6},
    { U1, R3},

    { L1, U3},
    { L4, U2},
    { L7, U1},

    { D7, L1},
    { D8, L4},
    { D9, L7},
  };
  public static int[][] Bm_pattern = reverse_pattern(B_pattern);

  public static int[][] L_pattern = {
    { L1, L7},
    { L2, L4},
    { L3, L1},
    { L4, L8},
    { L6, L2},
    { L7, L9},
    { L8, L6},
    { L9, L3},

    { F1, U1},
    { F4, U4},
    { F7, U7},

    { U1, B1},
    { U4, B4},
    { U7, B7},

    { B7, D7},
    { B4, D4},
    { B1, D1},

    { D1, F1},
    { D4, F4},
    { D7, F7},
  };
  public static int[][] Lm_pattern = reverse_pattern(L_pattern);

  public static int[][] T_pattern = {
    { U1, U7},
    { U2, U4},
    { U3, U1},
    { U4, U8},
    { U6, U2},
    { U7, U9},
    { U8, U6},
    { U9, U3},

    { B7, L3},
    { B8, L2},
    { B9, L1},

    { R3, B7},
    { R2, B8},
    { R1, B9},

    { F1, R1},
    { F2, R2},
    { F3, R3},

    { L1, F1},
    { L2, F2},
    { L3, F3},
  };
  public static int[][] Tm_pattern = reverse_pattern(T_pattern);

  public static int[][] D_pattern= {
    { D1, D7},
    { D2, D4},
    { D3, D1},
    { D4, D8},
    { D6, D2},
    { D7, D9},
    { D8, D6},
    { D9, D3},

    { F7, L7},
    { F8, L8},
    { F9, L9},

    { R7, F7},
    { R8, F8},
    { R9, F9},

    { B1, R9},
    { B2, R8},
    { B3, R7},

    { L9, B1},
    { L8, B2},
    { L7, B3},
  };
  public static int[][] Dm_pattern = reverse_pattern(D_pattern);

  public static int[] create_empty_cube() {
    int[] res=  new int[CUBE_CELLS];
    for (int i = 0; i < res.length; i++) {
      res[i] = 0;
    }
    return res;
  }

  public static int[] create_complete_cube() {
	int[] res=  new int[CUBE_CELLS];
	for(int i = F1;i<=F9;i++) {
	 res[i] = 1;
        }
	for(int i = U1;i<=U9;i++) {
	 res[i] = 2;
        }
	for(int i = R1;i<=R9;i++) {
	 res[i] = 3;
        }
	for(int i = D1;i<=D9;i++) {
	 res[i] = 4;
        }
	for(int i = L1;i<=L9;i++) {
	 res[i] = 5;
        }
	for(int i = B1;i<=B9;i++) {
	 res[i] = 6;
        }
        return res;
  }

  private static String cube_first_line(char faceName) {
    return faceName+"--+--+--";
  }

  private static String cube_first_line_end() {
    return "+";
  }
  private static String cube_line_end() {
    return "|";
  }

  private static String cube_first_line() {
    return "+--+--+--";
  }


  private static String cube_space() {
    return "         ";

  }

  private static String cell_to_string(int cell) {
   if (cell<10) return " "+cell;
   return ""+cell;

  }
  private static String cube_line_to_string(int first_cell_of_face, int[] cube) {
     return "|"+cell_to_string(cube[first_cell_of_face])+"|"+cell_to_string(cube[first_cell_of_face+1])+"|"+cell_to_string(cube[first_cell_of_face+2]);
  }
  private static String cube_inv_line_to_string(int first_cell_of_face, int[] cube) {
     return "|"+cell_to_string(cube[first_cell_of_face+2])+"|"+cell_to_string(cube[first_cell_of_face+1])+"|"+cell_to_string(cube[first_cell_of_face]);
  }

  public static String cube_to_string(String[] captions, int[][] cubes, int delim) {
    String[] s = new String[captions.length];
    List[] sLines = new List[s.length];
    int[] max_width = new int[s.length];
    StringTokenizer st = null;
    for (int i = 0; i < s.length; i++) {
      s[i] = cube_to_string(cubes[i]);
      sLines[i] = new ArrayList();
      if (captions[i]!=null) { sLines[i].add(captions[i]); }
      st = new StringTokenizer(s[i],nr);
      max_width[i] = -1;
      while (st.hasMoreElements()) {
        String o = (String)st.nextElement();
        sLines[i].add(o);
        if (o.length()> max_width[i]) {max_width[i] = o.length();}
      }
      max_width[i] += delim;
    }

    StringBuffer sb = new StringBuffer();
    for (int i = 0; i < sLines[0].size(); i++) {
      for (int j = 0; j < sLines.length; j++) {
        String t1 = (String)sLines[j].get(i);
        while (t1.length()<max_width[j]) {t1 = t1+" ";}
        sb.append(t1);
      }
      sb.append(nr);
    }
    return sb.toString();
  }


  public static String cube_to_hash_string(int[] cube) {
    StringBuffer sb = new StringBuffer();
    for (int i=0;i<CUBE_CELLS;i++) sb.append(""+cube[i]);
    return sb.toString();
  }

  public static String cube_to_string(int[] cube) {
     StringBuffer sb = new StringBuffer();
     sb.append( cube_space());
     sb.append( cube_first_line('T'));
     sb.append( cube_first_line_end());
     sb.append( nr);

     for (int i = 0; i<3;i++) {
       sb.append( cube_space());
       sb.append( cube_line_to_string(U1+3*i, cube));
       sb.append( cube_line_end());
       sb.append( nr);
     }
     sb.append( cube_first_line('L'));
     sb.append( cube_first_line('F'));
     sb.append( cube_first_line('R'));
    sb.append( cube_first_line_end());
     sb.append( nr);
     for (int i = 0; i<3;i++) {
       sb.append( cube_line_to_string(L1+3*i, cube));
       sb.append( cube_line_to_string(F1+3*i, cube));
       sb.append( cube_line_to_string(R1+3*i, cube));
       sb.append( cube_line_end());
       sb.append( nr);
     }
     sb.append( cube_first_line());
     sb.append( cube_first_line('D'));
     sb.append( cube_first_line());
     sb.append( cube_first_line_end());
     sb.append( nr);
     for (int i = 0; i<3;i++) {
       sb.append( cube_space());
       sb.append( cube_line_to_string(D1+3*i, cube));
       sb.append( cube_line_end());
       sb.append( nr);
     }
    sb.append( cube_space());
    sb.append( cube_first_line('B'));
    sb.append( cube_first_line_end());

    sb.append( nr);
    for (int i = 0; i<3;i++) {
      sb.append( cube_space());
      sb.append( cube_line_to_string(B1+3*i, cube));
      sb.append( cube_line_end());
      sb.append( nr);
    }
     sb.append( cube_space());
     sb.append( cube_first_line());
     sb.append( cube_first_line_end());
     sb.append( nr);
     return sb.toString();
  }


  private static int transport_cell(int cell, int TF1,int TU1,int TR1,int TD1,int TL1,int TB1) {
    int base = -1;
    int delta = -1;
    int[] mapped_bases = {TF1,TU1,TR1,TD1,TL1,TB1};
    int[] bases = {F1,U1,R1,D1,L1,B1};
    for (int i = 0; i < bases.length; i++) {
      int bas = bases[i];
      if ((cell>=bas)&&(cell<=bas+8)) {
        base = i;
        delta = cell-bas;
        break;
      }
    }
    if (base==-1) {
      throw new IllegalArgumentException("cell ="+cell);
    }
    int res = mapped_bases[base]+delta;
    return res;
  }

  private static int[][]transport_pattern(int[][] pattern, int TF1,int TU1,int TR1,int TD1,int TL1,int TB1) {
    int[][] res = new int[pattern.length][2];
    for (int i = 0; i < res.length; i++) {
      res[i][0] = transport_cell(pattern[i][0],TF1,TU1,TR1,TD1,TL1,TB1) ;
      res[i][1] = transport_cell(pattern[i][1],TF1,TU1,TR1,TD1,TL1,TB1) ;
    }
    return res;
  }

  private static int[][] reverse_pattern(int[][] pattern) {
    int[][] res = new int[pattern.length][2];
    for (int i = 0; i < res.length; i++) {
      res[i][0] = pattern[i][1];
      res[i][1] = pattern[i][0];
    }
    return res;
  }
  
  
  /**@deprecated*/ 
  private static int[] apply_move_pattern(int[] cube, int pattern[][]) {
    int[] res = copy(cube);
    for (int i = 0; i < pattern.length; i++) {
      int[] change = pattern[i];
      res[change[0]] = cube[change[1]];
    }
    return res;
  }
  
  
  public static void undo_move(char move, int[] cube, int[] target_cube) {
	move(inverse_move(move),cube, target_cube);
  }

  public static void move(String moves, int[] cube, int[] target_cube) {
    move(moves.toCharArray(), cube, target_cube);
  }

  public static void move(char move, int[] cube, int[] target_cube) {
    int[][] pattern = get_move_pattern(move);
    apply_move_pattern(cube, pattern, target_cube);
  }
  public static void move (char[] moves, int[] cube, int[] target_cube) {
	Cube.copy(cube, target_cube);
	for (int i = 0; i< moves.length;i++) {
	  move(moves[i], target_cube, target_cube);
    }
  }

  
  static int[] tmp_cube = Cube.create_empty_cube();
  private static int[] apply_move_pattern(int[] cube, int pattern[][], int[] target_cube) {
	  Cube.copy(cube, tmp_cube);
	    for (int i = 0; i < pattern.length; i++) {
	      int[] change = pattern[i];
	      tmp_cube[change[0]] = cube[change[1]];
	    }
	    Cube.copy(tmp_cube, target_cube);
	    return target_cube;
  }
  

  

  /**@deprecated*/ 
  public static int[] undo_move(char move, int[] cube) {
	return move(inverse_move(move),cube);
  }

  /**@deprecated*/ 
  public static int[] move(String moves, int[] cube) {
    return move(moves.toCharArray(), cube);
  }

  /**@deprecated*/ 
  public static int[] move(char move, int[] cube) {
    int[][] pattern = get_move_pattern(move);
    int[] res = apply_move_pattern(cube, pattern);
    return res;
  }
  /**@deprecated*/ 
  public static int[] move (char[] moves, int[] cube) {
    int[] res;
	res = copy(cube);
	for (int i = 0; i< moves.length;i++) {
	  res = move(moves[i], res);
        }
	return res;
  }


  public static String cellName(int cell) {
    int delta = -1;
    int base = -1;
    String[] names = {"F","U","R","D","L","B"};
    int[] bases = {F1,U1,R1,D1,L1,B1};
    for (int i = 0; i < bases.length; i++) {
      int bas = bases[i];
      if ((cell>=bas)&&(cell<=bas+8)) {
        base = i;
        delta = cell-bas;
        break;
      }
    }
    if (base==-1) {
      throw new IllegalArgumentException("cell ="+cell);
    }
    String res = names[base]+(delta+1);
    return res;

  }

  public static int[][] get_move_pattern(char move) {
    switch (move) {
      case 'F':
        return F_pattern;
      case 'f':
        return Fm_pattern;
      case 'R':
        return R_pattern;
      case 'r':
        return Rm_pattern;
      case 'B':
        return B_pattern;
      case 'b':
        return Bm_pattern;
      case 'L':
        return L_pattern;
      case 'l':
        return Lm_pattern;
      case 'T':
        return T_pattern;
      case 't':
        return Tm_pattern;
      case 'D':
        return D_pattern;
      case 'd':
        return Dm_pattern;
    }
    throw new IllegalArgumentException("move ="+move);
  }
  public static void printPattern(int[][] pattern) {
    for (int j = 0; j < 2; j++) {
      for (int i = 0; i < pattern.length; i++) {
        int cell = pattern[i][j];
        System.out.print(cellName(cell)+" ");
      }
      System.out.println();
    }
  }
  public Cube() {
  }

  public static boolean equals(int[] cube, int[] cube_pattern) {
	for (int i=0; i<CUBE_CELLS; i++) {
	   if (cube[i]>0) {
             if (cube[i]!=cube_pattern[i]) {
               return false;
             }
           }
        }
	return true;
  }

  public static char[] inverse_move(char[] moves) {
    char[] im = new char[moves.length];
    for (int i = 0; i < im.length; i++) {
      im[i] = inverse_move(moves[moves.length-i-1]);
    }
    return im;
  }

  public static String inverse_move(String moves) {
    return new String(inverse_move(moves.toCharArray()));
  }
  public static char inverse_move(char move) {
    switch (move) {
      case 'F':
        return 'f';
      case 'f':
        return 'F';
      case 'T':
        return 't';
      case 't':
        return 'T';
      case 'R':
        return 'r';
      case 'r':
        return 'R';
      case 'D':
        return 'd';
      case 'd':
        return 'D';
      case 'L':
        return 'l';
      case 'l':
        return 'L';
      case 'B':
        return 'b';
      case 'b':
        return 'B';
    }
    throw new IllegalArgumentException("wrong move: "+move);
  }

  private static int[] read_numbers(String str) {
    StringTokenizer st = new StringTokenizer(str, " |+LFRTDB");
    int[] res= new int[st.countTokens()];
    for (int i = 0; i < res.length; i++) {
      try {
        res[i] = Integer.parseInt(st.nextToken());
      }
      catch (NumberFormatException ex) {
        return null;
      }
    }
    return res;
  }
  public static int[][] read_cube(String str) {
    StringTokenizer st = new StringTokenizer(str, nr);
    List list= new ArrayList();
    while (st.hasMoreElements()) {
      list.add(st.nextToken());
    }
    return read_cube(list);
  }

  public static int[][] read_cube(List stringList) {
    final int MODE_T = 1;
    final int MODE_LFR = 2;
    final int MODE_D = 3;
    final int MODE_B = 4;
    final int MODE_STOP = 5;


    int mode = MODE_T;
    int delta = 0;
    int[][] cubes = new int[10][];
    int cubes_number = 0;


    for (int i = 0; i < stringList.size(); i++) {
      String str = (String)stringList.get(i);
      int[] nums = read_numbers(str);
      if (nums!=null) {
        switch (mode) {
          case MODE_T:
            for (int j = 0; j < nums.length/3; j++) {
              if (cubes[j]==null) {cubes[j] = Cube.create_empty_cube(); cubes_number = j+1; }
              cubes[j][U1+(delta*3)] = nums[3*j+0];
              cubes[j][U2+(delta*3)] = nums[3*j+1];
              cubes[j][U3+(delta*3)] = nums[3*j+2];
            }
            delta += 1;
            if (delta == 3) {
              mode = MODE_LFR;
              delta = 0;
            }
            break;
          case MODE_LFR:
            for (int j = 0; j < nums.length/9; j++) {
              if (cubes[j]==null) {cubes[j] = Cube.create_empty_cube(); }
              cubes[j][L1+(delta*3)] = nums[9*j+0];
              cubes[j][L2+(delta*3)] = nums[9*j+1];
              cubes[j][L3+(delta*3)] = nums[9*j+2];
              cubes[j][F1+(delta*3)] = nums[9*j+3];
              cubes[j][F2+(delta*3)] = nums[9*j+4];
              cubes[j][F3+(delta*3)] = nums[9*j+5];
              cubes[j][R1+(delta*3)] = nums[9*j+6];
              cubes[j][R2+(delta*3)] = nums[9*j+7];
              cubes[j][R3+(delta*3)] = nums[9*j+8];
            }

            delta += 1;
            if (delta == 3) {
              mode = MODE_D;
              delta = 0;
            }
            break;
          case MODE_D:
            for (int j = 0; j < nums.length/3; j++) {
              if (cubes[j]==null) {cubes[j] = Cube.create_empty_cube(); }
              cubes[j][D1+(delta*3)] = nums[3*j+0];
              cubes[j][D2+(delta*3)] = nums[3*j+1];
              cubes[j][D3+(delta*3)] = nums[3*j+2];
            }
            delta += 1;
            if (delta == 3) {
              mode = MODE_B;
              delta = 0;
            }
            break;
          case MODE_B:
            for (int j = 0; j < nums.length/3; j++) {
              if (cubes[j]==null) {cubes[j] = Cube.create_empty_cube(); }
              cubes[j][B1+(delta*3)] = nums[3*j+0];
              cubes[j][B2+(delta*3)] = nums[3*j+1];
              cubes[j][B3+(delta*3)] = nums[3*j+2];
            }
            delta += 1;
            if (delta == 3) {
              mode = MODE_STOP;
              delta = 0;
            }
            break;
        }
      }

    }
    int[][] res = new int[cubes_number][];
    for (int i = 0; i < res.length; i++) {
      res[i] = cubes[i];
    }
    return res;
  }
  
  
  public static char[] copyChars(char[] source, int from, int to) {
		char[] result = new char[to - from];
		for (int i = 0; i < result.length; i++) {
			if ((from + i) < source.length) {
				result[i] = source[from + i];
			} else {
				result[i] = ' ';
			}
		}
		return result;
	}
  
  
  public static int cube_to_indicator_hash(int[] cube, int[] indicator) {
	  int[] ind = new int[CUBE_CELLS];
	  int cnt = 0;
	  for (int i=0;i<CUBE_CELLS;i++) {
	    	if(indicator[i]==1) {
		    	ind[cnt]=cube[i];
		    	cnt++;
	    	}
	  }
	  return HashCodeUtils.computeHashCodeForArray(ind);
  	}
	
  
  public static String cube_to_indicator_string_old(int[] cube, int[] indicator) {
	    StringBuffer sb = new StringBuffer();
	    for (int i=0;i<CUBE_CELLS;i++) {
	    	if(indicator[i]==1) {
		    	sb.append(""+cube[i]);
	    	} else if (indicator[i]==0) {
	    		
	    	} else {
	    		throw new RuntimeException("Unexpected indicator value "+ indicator[i]+" in position "+i);
	    	}
	    }
	    return sb.toString();
	}
	

	public static char[] toChars(List list) {
		char[] chars = new char[list.size()];
		for (int i = 0; i < list.size(); i++) {
			char c = ((Character) list.get(i)).charValue();
			chars[i] = c;
		}
		return chars;
	}


}